package 二叉树.练习;

//
import 二叉树.基础.TreeNode;
//找到该树中两个指定节点的最近公共祖先
import java.util.Stack;

public class Text_9 {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        if(root == null){
            return null;
        }
        //只要其中一个为根节点，那么这个最近一定为根节点
        if(p==root||q==root){
            return root;
        }
        TreeNode leftNode = lowestCommonAncestor(root.left,p,q);
        TreeNode rightNode = lowestCommonAncestor(root.right,p,q);

        //情况：1，左边右边都不为空，返回根节点
//        2.左边不为空，右边为空，只讨论左边
//        3.左边为空，右边不为空，只讨论右边
        if(leftNode!=null&&rightNode!=null){
            return root;
        }else if(leftNode!=null&&rightNode==null){
            return leftNode;
        }else {
            return rightNode;
        }
    }



    //方法2
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if(root==null||node ==null){
            return false;
        }
        stack.push(root);
        if(root ==node){
            return true;
        }
        boolean b1 = getPath(root.left,node,stack);
        if(b1 ==true){
            return true;
        }
        boolean b2 = getPath(root.right,node,stack);
        if (b2 == true){
            return true;
        }
        //找了都没有，返回删掉这个数
        stack.pop();
        return false;
    }

    public TreeNode lowestCommonAncestor1(TreeNode root,TreeNode p,TreeNode q){
        if(root ==null){
            return null;
        }
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();
        getPath(root,p,stackP);
        getPath(root,q,stackQ);

        int lenP = stackP.size();
        int lenQ = stackQ.size();
        int len = 0;
        if(lenP>lenQ){
            len = lenP-lenQ;
            while(len>0){
                stackP.pop();
                len--;
            }
        }else {
            len = lenQ-lenP;
            while (len>0){
                stackQ.pop();
                len--;
            }
        }

        while (!stackP.isEmpty()){
            if(stackP.peek().equals(stackQ.peek())){
                return stackP.peek();
            }else {
                stackP.pop();
                stackQ.pop();
            }
        }

        return null;
    }
}
